home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / bool_lib / bool1low.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-26  |  48.1 KB  |  1,205 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d (not only polygonal) solid modeller.             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle the low level boolean operations. The routines in this  *
  7. * module should be accessed from "bool-hi.c" module only.             *
  8. *   Note the polygons of the two given objects may not be convex, and must   *
  9. * be subdivided into convex ones in the boolean upper level routines (module *
  10. * bool-hi.c). All the routines of this module expects objects with convex    *
  11. * polygons only although they might return objects with non convex polygons, *
  12. * but marked as so (via polygons CONVEX tags - see IPPolygonStruct def.)!    *
  13. *   Because Bool-low.c module was too big, it was subdivided to two:         *
  14. * Bool1Low.c - mainly handles the intersection polyline between the oper.    *
  15. * Bool2Low.c - mainly handles the polygon extraction from operands given the *
  16. *           polyline of intersection and the adjacencies (see ADJACNCY.C) *
  17. * Note we said mainly has routines CAN call one another!             *
  18. *****************************************************************************/
  19.  
  20. /* #define DEBUG2             If defined, defines some printing routines. */
  21. /* #define DEBUG3             Print messages to entry/exit from routines. */
  22.  
  23. #include <stdio.h>
  24. #include <ctype.h>
  25. #include <math.h>
  26. #include <string.h>
  27. #include "irit_sm.h"
  28. #include "allocate.h"
  29. #include "bool_loc.h"
  30. #include "geomat3d.h"
  31.  
  32. static int
  33.     GlblObjsIntersects,
  34.     GlblPolySortAxis = 0;
  35.  
  36. static IPObjectStruct *BooleanLowGenInOut(IPObjectStruct *PObj1, int InOut);
  37. static void BooleanLowInterAll(IPObjectStruct *PObj1, IPObjectStruct *PObj2);
  38. static void BooleanLowInterOne(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2);
  39. static InterSegmentStruct *InterSegmentPoly(IPPolygonStruct *Pl,
  40.                         IPPolygonStruct *SegPl,
  41.                         PointType Segment[2]);
  42. static void SwapPointInterList(InterSegmentStruct *PSeg);
  43. static void DeleteSegInterList(InterSegmentStruct *PSeg,
  44.                    InterSegmentStruct **PSegList);
  45. static InterSegmentStruct *FindMatchInterList(PointType Pt,
  46.                           InterSegmentStruct **PSegList);
  47. static void SortOpenReverseLoop(SortOpenStruct *PSHead);
  48. static RealType SortOpenInsertOne(SortOpenStruct **PSHead,
  49.                   SortOpenStruct *PSTemp,
  50.                   PointType Pt,
  51.                   IPVertexStruct *V,
  52.                   IPPolygonStruct *Pl);
  53. static IPObjectStruct *PolylineFromInterSeg(IPObjectStruct *PObj);
  54. #if defined(ultrix) && defined(mips)
  55. static int BooleanPrepObjectCmpr(VoidPtr VPoly1, VoidPtr VPoly2);
  56. #else
  57. static int BooleanPrepObjectCmpr(const VoidPtr VPoly1, const VoidPtr VPoly2);
  58. #endif /* ultrix && mips (no const support) */
  59. static void BooleanPrepObject(IPObjectStruct *PObj);
  60.  
  61. #ifdef DEBUG2
  62. static void PrintVrtxList(IPVertexStruct *V);
  63. static void PrintInterList(InterSegmentStruct *PInt);
  64. #endif /* DEBUG2 */
  65.  
  66. /*****************************************************************************
  67. * DESCRIPTION:                                                               M
  68. *   Finds the part of PObj1 which is out of PObj2:                 M
  69. *                                                                            *
  70. * PARAMETERS:                                                                M
  71. *   PObj1:    First object of Boolean operation.                             M
  72. *   PObj2:    Second object of Boolean operation.                            M
  73. *                                                                            *
  74. * RETURN VALUE:                                                              M
  75. *   IPObjectStruct: Result of one out two.                                   M
  76. *                                                                            *
  77. * KEYWORDS:                                                                  M
  78. *   BooleanLow1Out2, Booleans                                                M
  79. *****************************************************************************/
  80. IPObjectStruct *BooleanLow1Out2(IPObjectStruct *PObj1, IPObjectStruct *PObj2)
  81. {
  82. #ifdef DEBUG3
  83.     printf("Enter BooleanLow1Out2\n");
  84. #endif /* DEBUG3 */
  85.  
  86.     BoolGenAdjacencies(PObj1);
  87.  
  88.     /* Find all intersections of PObj1 polygons with PObj2 polygons. */
  89.     GlblObjsIntersects = FALSE;
  90.     BooleanLowInterAll(PObj1, PObj2);
  91.  
  92.     /* Generate all the polygons in PObj1 which are out of PObj2. */
  93.     if (!GlblObjsIntersects) {
  94.     FatalBooleanError(FTL_BOOL_NO_INTER);
  95.     }
  96.  
  97.     return BooleanLowGenInOut(PObj1, FALSE);
  98. }
  99.  
  100. /*****************************************************************************
  101. * DESCRIPTION:                                                               M
  102. *   Finds the part of PObj1 which is in of PObj2:                 M
  103. *                                                                            *
  104. * PARAMETERS:                                                                M
  105. *   PObj1:    First object of Boolean operation.                             M
  106. *   PObj2:    Second object of Boolean operation.                            M
  107. *                                                                            *
  108. * RETURN VALUE:                                                              M
  109. *   IPObjectStruct: Result of one in two.                                    M
  110. *                                                                            *
  111. * KEYWORDS:                                                                  M
  112. *   BooleanLow1In2, Booleans                                                 M
  113. *****************************************************************************/
  114. IPObjectStruct *BooleanLow1In2(IPObjectStruct *PObj1, IPObjectStruct *PObj2)
  115. {
  116. #ifdef DEBUG3
  117.     printf("Enter BooleanLow1In2\n");
  118. #endif /* DEBUG3 */
  119.  
  120.     BoolGenAdjacencies(PObj1);
  121.  
  122.     /* Find all intersections of PObj1 polygons with PObj2 polygons. */
  123.     GlblObjsIntersects = FALSE;
  124.     BooleanLowInterAll(PObj1, PObj2);
  125.  
  126.     /* Generate all the polygons in PObj1 which are in PObj2. */
  127.     if (!GlblObjsIntersects) {
  128.     FatalBooleanError(FTL_BOOL_NO_INTER);
  129.     }
  130.     return BooleanLowGenInOut(PObj1, TRUE);
  131. }
  132.  
  133. /*****************************************************************************
  134. * DESCRIPTION:                                                               *
  135. *   Scans the InterSegmentList of each polygon and decides using Inter.      *
  136. * list, if it is IN relative to the other object. Note that for polygons     *
  137. * that do not intersect at all, we use the polygon adjacencies to decide     *
  138. * if they are IN or not.                             *
  139. *                                                                            *
  140. * PARAMETERS:                                                                *
  141. *   PObj:      To decide if it is in out out.                                *
  142. *   InOut:     What are we looking for? in or out.                           *
  143. *                                                                            *
  144. * RETURN VALUE:                                                              *
  145. *   IPObjectStruct:   Resulting set of polygons that are in the requested    *
  146. *                     half space.                                            *
  147. *****************************************************************************/
  148. static IPObjectStruct *BooleanLowGenInOut(IPObjectStruct *PObj, int InOut)
  149. {
  150.     if (BoolOutputInterCurve) {
  151.     /* Return a polyline object - extract the InterSegment list of each */
  152.     /* polygon into open/closed polyline loops object.            */
  153.     return PolylineFromInterSeg(PObj);
  154.     }
  155.     else {
  156.     if (BoolHandleCoplanarPoly) {
  157.         IPObjectStruct
  158.         *PObjNew = BoolExtractPolygons(PObj, InOut);
  159.         IPPolygonStruct
  160.         *Pl = PObjNew -> U.Pl;
  161.  
  162.         /* Purge all polygons that were tagged being coplanar. */
  163.         while (Pl != NULL && IS_COPLANAR_POLY(Pl)) {
  164.             PObjNew -> U.Pl = PObjNew -> U.Pl -> Pnext;
  165.             IPFreePolygon(Pl);
  166.         Pl = PObjNew -> U.Pl;
  167.         }
  168.         if (Pl != NULL) {
  169.         while (Pl -> Pnext != NULL) {
  170.             if (IS_COPLANAR_POLY(Pl -> Pnext)) {
  171.             IPPolygonStruct
  172.                 *PlTemp = Pl -> Pnext;
  173.  
  174.             Pl -> Pnext = PlTemp -> Pnext;
  175.             IPFreePolygon(PlTemp);
  176.                 }
  177.                 else
  178.                 Pl = Pl -> Pnext;
  179.         }
  180.         }
  181.  
  182.         return PObjNew;
  183.     }
  184.     else
  185.         return BoolExtractPolygons(PObj, InOut);
  186.     }
  187. }
  188.  
  189. /*****************************************************************************
  190. * DESCRIPTION:                                                               *
  191. *   Creates a polyline object out of the intersection list of the polygons.  *
  192. *                                                                            *
  193. * PARAMETERS:                                                                *
  194. *   PObj:     Polygon for which intersection loops are to be formed.         *
  195. *                                                                            *
  196. * RETURN VALUE:                                                              *
  197. *   IPObjectStruct:  Resulting loops.                                        *
  198. *****************************************************************************/
  199. static IPObjectStruct *PolylineFromInterSeg(IPObjectStruct *PObj)
  200. {
  201.     IPObjectStruct *PObjRet;
  202.     IPPolygonStruct *PlTemp, *PlObj,
  203.     *PlHead = NULL;
  204.     InterSegmentStruct *PInter, *PInterNext;
  205.     InterSegListStruct *PClosed, *POpen, *PClosedNext, *POpenNext;
  206.     IPVertexStruct *V;
  207.  
  208.     PlObj = PObj -> U.Pl;
  209.     while (PlObj != NULL) {
  210.     BoolLoopsFromInterList(PlObj, &PClosed, &POpen);
  211.     while (POpen != NULL) {
  212.         /* Make one polyline from each loop in list: */
  213.         PInter = POpen -> PISeg;
  214.         POpenNext = POpen -> Pnext;
  215.  
  216.         PlTemp = IPAllocPolygon(0, 0, NULL, NULL);
  217.         PlTemp -> PVertex = V = IPAllocVertex(0, 0, NULL, NULL);
  218.         PT_COPY(V -> Coord, PInter -> PtSeg[0]);
  219.         while (PInter) {
  220.         PInterNext = PInter -> Pnext;
  221.  
  222.         V -> Pnext = IPAllocVertex(0, 0, NULL, NULL); V = V -> Pnext;
  223.         PT_COPY(V -> Coord, PInter -> PtSeg[1]);
  224.  
  225.         IritFree((VoidPtr) PInter);
  226.         PInter = PInterNext;
  227.         }
  228.         PlTemp -> Pnext = PlHead;
  229.         PlHead = PlTemp;
  230.  
  231.         IritFree((VoidPtr) POpen);
  232.         POpen = POpenNext;
  233.     }
  234.     while (PClosed != NULL) {
  235.         /* Make one polyline from each loop in list: */
  236.         PInter = PClosed -> PISeg;
  237.         PClosedNext = PClosed -> Pnext;
  238.  
  239.         PlTemp = IPAllocPolygon(0, 0, NULL, NULL);
  240.         PlTemp -> PVertex = V = IPAllocVertex(0, 0, NULL, NULL);
  241.         PT_COPY(V -> Coord, PInter -> PtSeg[0]);
  242.         while (PInter) {
  243.         V -> Pnext = IPAllocVertex(0, 0, NULL, NULL); V = V -> Pnext;
  244.         PT_COPY(V -> Coord, PInter -> PtSeg[1]);
  245.         PInter = PInter -> Pnext;
  246.         }
  247.         PlTemp -> Pnext = PlHead;
  248.         PlHead = PlTemp;
  249.  
  250.         IritFree((VoidPtr) PClosed);
  251.         PClosed = PClosedNext;
  252.     }
  253.     PlObj = PlObj -> Pnext;
  254.     }
  255.  
  256.     PObjRet = GenPolyObject("", PlHead, NULL);
  257.     IP_SET_POLYLINE_OBJ(PObjRet);        /* Mark it as polyline object. */
  258.     return PObjRet;
  259. }
  260.  
  261. /*****************************************************************************
  262. * DESCRIPTION:                                                               *
  263. *   Routine to compare two polygon's bbox value for sorting purposes.        *
  264. *                                                                            *
  265. * PARAMETERS:                                                                *
  266. *   VPoly1, VPoly2:  Two pointers to polygons.                               *
  267. *                                                                            *
  268. * RETURN VALUE:                                                              *
  269. *   int:   >0, 0, or <0 as the relation between the two polygons.            *
  270. *****************************************************************************/
  271. #if defined(ultrix) && defined(mips)
  272. static int BooleanPrepObjectCmpr(VoidPtr VPoly1, VoidPtr VPoly2)
  273. #else
  274. static int BooleanPrepObjectCmpr(const VoidPtr VPoly1, const VoidPtr VPoly2)
  275. #endif /* ultrix && mips (no const support) */
  276. {
  277.     RealType
  278.     Diff = (*((IPPolygonStruct **) VPoly1)) -> BBox[0][GlblPolySortAxis] -
  279.            (*((IPPolygonStruct **) VPoly2)) -> BBox[0][GlblPolySortAxis];
  280.  
  281.     return SIGN(Diff);
  282. }
  283.  
  284. /*****************************************************************************
  285. * DESCRIPTION:                                                               *
  286. *   Routine to compute BBox for all polygons in provided object PObj. Also,  *
  287. * the polygons are sorted in the list with according to their minimal BBox   *
  288. * value in GlblPolySortAxis axis.                         *
  289. *                                                                            *
  290. * PARAMETERS:                                                                *
  291. *   PObj:       To prepare.                                                  *
  292. *                                                                            *
  293. * RETURN VALUE:                                                              *
  294. *   void                                                                     *
  295. *****************************************************************************/
  296. static void BooleanPrepObject(IPObjectStruct *PObj)
  297. {
  298.     int i,
  299.     PolyCount = 0;
  300.     IPPolygonStruct **PlArray, **PlTemp,
  301.     *Pl = PObj -> U.Pl;
  302.  
  303.     /* Count how many polygons this object have and make sure all have bbox. */
  304.     while (Pl != NULL)
  305.     {
  306.     PolyCount++;
  307.  
  308.     if (BoolHandleCoplanarPoly)
  309.         RST_COPLANAR_POLY(Pl);
  310.  
  311.     if (!IP_HAS_BBOX_POLY(Pl)) {              /* Compute it now. */
  312.         RealType
  313.         *BBoxMin = Pl -> BBox[0],
  314.         *BBoxMax = Pl -> BBox[1];
  315.         IPVertexStruct
  316.         *V = Pl -> PVertex;
  317.  
  318.         BBoxMin[0] = BBoxMin[1] = BBoxMin[2] = INFINITY;
  319.         BBoxMax[0] = BBoxMax[1] = BBoxMax[2] = -INFINITY;
  320.  
  321.         do {
  322.             for (i = 0; i < 3; i++) {
  323.                 if (BBoxMin[i] > V -> Coord[i])
  324.             BBoxMin[i] = V -> Coord[i];
  325.                 if (BBoxMax[i] < V -> Coord[i])
  326.             BBoxMax[i] = V -> Coord[i];
  327.             }
  328.  
  329.         V = V -> Pnext;
  330.         }
  331.         while (V != NULL && V != Pl -> PVertex);
  332.  
  333.         IP_SET_BBOX_POLY(Pl);
  334.     }
  335.         
  336.         Pl = Pl -> Pnext;
  337.     }
  338.  
  339.     /* Sort the polygons with according to minimal BBox in GlblPolySortAxis. */
  340.     PlArray = (IPPolygonStruct **) IritMalloc(sizeof(IPPolygonStruct *) *
  341.                             PolyCount);
  342.     for (Pl = PObj -> U.Pl, PlTemp = PlArray; Pl != NULL; Pl = Pl -> Pnext)
  343.     *PlTemp++ = Pl;
  344.  
  345.     qsort(PlArray, PolyCount, sizeof(IPPolygonStruct *), BooleanPrepObjectCmpr);
  346.  
  347.     for (i = 1; i < PolyCount; i++)
  348.     PlArray[i - 1] -> Pnext = PlArray[i];
  349.     PlArray[PolyCount - 1] -> Pnext = NULL;
  350.     PObj -> U.Pl = PlArray[0];
  351.     IritFree((VoidPtr) PlArray);
  352. }
  353.  
  354. /*****************************************************************************
  355. * DESCRIPTION:                                                               M
  356. *  Routine to set polygonal sorting axis.                       M
  357. *                                                                            *
  358. * PARAMETERS:                                                                M
  359. *   PolySortAxis:    Sorting axis. Either 0(x), 1 (y), or 2 (z).             M
  360. *                                                                            *
  361. * RETURN VALUE:                                                              M
  362. *   void                                                                     M
  363. *                                                                            *
  364. * KEYWORDS:                                                                  M
  365. *   BoolSetPolySortAxis, Booleans                                            M
  366. *****************************************************************************/
  367. void BoolSetPolySortAxis(int PolySortAxis)
  368. {
  369.     GlblPolySortAxis = PolySortAxis;
  370. }
  371.  
  372. /*****************************************************************************
  373. * DESCRIPTION:                                                               *
  374. *   Routine to find all the intersections between all PObj1 polygons with    *
  375. * PObj2 polygons. The intersections are saved as a list of segments (struct  *
  376. * InterSegmentStruct) in each of PObj1 polygons using the PAux pointer (see  *
  377. * IPPolygonStruct). Note PObj2 is not modified at all, and in PObj1, only    *
  378. * PAux of each polygon is set to the segment list, or NULL if none.         *
  379. *                                                                            *
  380. * PARAMETERS:                                                                *
  381. *   PObj1:        First object to compute intersection for.                  *
  382. *   PObj2:        Second object to compute intersection for.                 *
  383. *                                                                            *
  384. * RETURN VALUE:                                                              *
  385. *   void                                                                     *
  386. *****************************************************************************/
  387. static void BooleanLowInterAll(IPObjectStruct *PObj1, IPObjectStruct *PObj2)
  388. {
  389.     IPPolygonStruct *Pl1, *Pl2, *Pl2Start;
  390.  
  391. #ifdef DEBUG3
  392.     printf("Enter BooleanLowInterAll\n");
  393. #endif /* DEBUG3 */
  394.  
  395.     /* Sort polygons and compute BBox for them if none exists. */
  396.     BooleanPrepObject(PObj1);
  397.     BooleanPrepObject(PObj2);
  398.     Pl2Start = PObj2 -> U.Pl;
  399.     
  400.     Pl1 = PObj1 -> U.Pl;
  401.     while (Pl1 != NULL) {
  402.     Pl1 -> PAux = NULL;       /* Empty InterSegment list to start with: */
  403.  
  404.     /* Intersect Pl1 against the Pl2 list until end of Pl2 list or       */
  405.     /* until the minimum of Pl2 polygon is larger than Pl1 maximum.      */
  406.     Pl2 = Pl2Start;
  407.     while (Pl2 != NULL &&
  408.            Pl1 -> BBox[1][GlblPolySortAxis] >=
  409.                     Pl2 -> BBox[0][GlblPolySortAxis]) {
  410.         if (Pl1 -> BBox[1][0] < Pl2 -> BBox[0][0] ||
  411.         Pl1 -> BBox[1][1] < Pl2 -> BBox[0][1] ||
  412.         Pl1 -> BBox[1][2] < Pl2 -> BBox[0][2] ||
  413.         Pl2 -> BBox[1][0] < Pl1 -> BBox[0][0] ||
  414.         Pl2 -> BBox[1][1] < Pl1 -> BBox[0][1] ||
  415.         Pl2 -> BBox[1][2] < Pl1 -> BBox[0][2]) {
  416.         /* The Bounding boxes do not intersect, skip polygons. */
  417.         }
  418.         else
  419.         BooleanLowInterOne(Pl1, Pl2);
  420.  
  421.         /* If Pl2 maximum is smaller than Pl1 minimum there is no reason */
  422.         /* to consider this Pl2 polygon any more as it cannot intersect  */
  423.         /* any more polygons in the Pl1 list.                            */
  424.         if (Pl2 -> BBox[1][GlblPolySortAxis] <
  425.                           Pl2 -> BBox[1][GlblPolySortAxis] &&
  426.         Pl2Start == Pl2)
  427.         Pl2Start = Pl2 -> Pnext;
  428.                                                         
  429.         Pl2 = Pl2 -> Pnext;
  430.     }
  431.  
  432.     if (Pl1 -> PAux != NULL)             /* If any intersection. */
  433.         GlblObjsIntersects = TRUE;
  434.  
  435.     Pl1 = Pl1 -> Pnext;
  436.     }
  437.  
  438. #ifdef DEBUG3
  439.     printf("Exit BooleanLowInterAll\n");
  440. #endif /* DEBUG3 */
  441. }
  442.  
  443. /*****************************************************************************
  444. * DESCRIPTION:                                                               *
  445. *   Routine to intersect polygon Pl1, with polygon Pl2. If found common      *
  446. * intersection, that segment will be added to the InterSegmentStruct list    *
  447. * saved in Pl1 PAux list.                             *
  448. *   Note that as the two polygons convex, at most one line segment can       *
  449. * result from such intersection (of two non coplanar polygons).             *
  450. *   Algorithm: intersect all Pl2 edges with Pl1 plane. If found that         *
  451. * (exactly) two vertices (one segment) of Pl2 do intersect Pl1 plane then:   *
  452. * Perform clipping of the segment against Pl1. If result is not empty, add   *
  453. * the result segment to Pl1 InterSegmentStruct list (saved at PAux of         *
  454. * polygon - see IPPolygonStruct).                         *
  455. *                                                                            *
  456. * PARAMETERS:                                                                *
  457. *   Pl1:       First polygon to compute intersection for.                    *
  458. *   Pl2:       Second polygon to compute intersection for.                   *
  459. *                                                                            *
  460. * RETURN VALUE:                                                              *
  461. *   void                                                                     *
  462. *****************************************************************************/
  463. static void BooleanLowInterOne(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2)
  464. {
  465.     int NumOfInter = 0;
  466.     RealType TInter[2],
  467.     *Plane1 = Pl1 -> Plane,                   /* For faster access. */
  468.     *Plane2 = Pl2 -> Plane;
  469.     PointType Inter[2], Dir;
  470.     IPVertexStruct *Vnext,
  471.     *V = Pl2 -> PVertex;
  472.     InterSegmentStruct *PSeg, *PLSeg;
  473.  
  474. #ifdef DEBUG3
  475.     printf("Enter BooleanLowInterOne\n");
  476. #endif /* DEBUG3 */
  477.  
  478.     if ((BOOL_APX_EQ(Plane1[0], Plane2[0]) &&
  479.      BOOL_APX_EQ(Plane1[1], Plane2[1]) &&
  480.      BOOL_APX_EQ(Plane1[2], Plane2[2]) &&
  481.      BOOL_APX_EQ(Plane1[3], Plane2[3])) ||
  482.     (BOOL_APX_EQ(Plane1[0], -Plane2[0]) &&
  483.      BOOL_APX_EQ(Plane1[1], -Plane2[1]) &&
  484.      BOOL_APX_EQ(Plane1[2], -Plane2[2]) &&
  485.      BOOL_APX_EQ(Plane1[3], -Plane2[3]))) {
  486.     /* The two polygons are coplanar, do not attempt to intersect. */
  487.     if (BoolHandleCoplanarPoly) {
  488.         SET_COPLANAR_POLY(Pl1);
  489.         SET_COPLANAR_POLY(Pl2);
  490.     }
  491.     else {
  492.         IritWarningError("Boolean: coplanar polygons detected. Enable COPLANAR state.");
  493.     }
  494.     }
  495.     else {
  496.     do {
  497.         Vnext = V -> Pnext;
  498.         PT_SUB(Dir, Vnext -> Coord, V -> Coord);
  499.         if (CGPointFromLinePlane01(V -> Coord, Dir, Plane1,
  500.                  Inter[NumOfInter], &TInter[NumOfInter]) &&
  501.             ((NumOfInter == 0) || (NumOfInter == 1 &&
  502.                        !BOOL_PT_APX_EQ(Inter[0], Inter[1]))))
  503.             NumOfInter++;
  504.         if (NumOfInter == 2)
  505.         break;               /* Cannt have more intersections. */
  506.  
  507.         V = Vnext;
  508.     }
  509.     while (V != NULL && V != Pl2 -> PVertex);
  510.     }
  511.  
  512.     switch (NumOfInter) {
  513.     case 0:
  514.         break;
  515.     case 1:
  516.         /* One intersection is possible if only one vertex of Pl2 is in  */
  517.         /* the plane of Pl1, all other vertices are on one side of plane.*/
  518.         break;
  519.     case 2:
  520.         /* Clip the segment against the polygon and insert if not empty: */
  521.         if ((PSeg = InterSegmentPoly(Pl1, Pl2, Inter)) != NULL) {
  522.         /* insert that segment to list of Pl1. Note however that the */
  523.         /* intersection may be exactly on 2 other polygons boundary, */
  524.         /* And therefore creates the same intersection edge TWICE!   */
  525.         /* Another possiblity is on same case, the other polygon     */
  526.         /* will have that inter. edge on its edge, and its ignored.  */
  527.         /* We therefore test for duplicates and ignore edge if so.   */
  528.         if (PSeg -> V[0] != NULL && PSeg -> V[0] == PSeg -> V[1]) {
  529.             IritFree((VoidPtr) PSeg);               /* Ignore it! */
  530.             return;
  531.         }
  532.         PLSeg = (InterSegmentStruct *) Pl1 -> PAux;
  533.         while (PLSeg != NULL) {
  534.             if ((BOOL_PT_APX_EQ(PSeg -> PtSeg[0], PLSeg -> PtSeg[0]) &&
  535.              BOOL_PT_APX_EQ(PSeg -> PtSeg[1], PLSeg -> PtSeg[1])) ||
  536.             (BOOL_PT_APX_EQ(PSeg -> PtSeg[0], PLSeg -> PtSeg[1]) &&
  537.              BOOL_PT_APX_EQ(PSeg -> PtSeg[1], PLSeg -> PtSeg[0]))) {
  538.             IritFree((VoidPtr) PSeg);           /* Ignore it! */
  539.             return;
  540.             }
  541.             PLSeg = PLSeg -> Pnext;
  542.         }
  543.  
  544.         PSeg -> Pnext = (InterSegmentStruct *) Pl1 -> PAux;
  545.         Pl1 -> PAux = (VoidPtr) PSeg;
  546.         }
  547.         break;
  548.     }
  549.  
  550. #ifdef DEBUG3
  551.     printf("Exit BooleanLowInterOne\n");
  552. #endif /* DEBUG3 */
  553. }
  554.  
  555. /*****************************************************************************
  556. * DESCRIPTION:                                                               *
  557. *   Intersects the given segment (given as two end points), with the given   *
  558. * polygon (which must be convex). Upto two intersections are possible, as    *
  559. * again, the polygon is convex. Note Segment polygon is given as SegPl.      *
  560. *                                                                            *
  561. * PARAMETERS:                                                                *
  562. *   Pl:           Full complete polygon.                                     *
  563. *   SegPl:        Origin of Segment.                                         *
  564. *   Segment:      A single linear segment as two points.                     *
  565. *                                                                            *
  566. * RETURN VALUE:                                                              *
  567. *   InterSegmentStruct:      The (upto) two intersections information.       *
  568. *****************************************************************************/
  569. static InterSegmentStruct *InterSegmentPoly(IPPolygonStruct *Pl,
  570.                         IPPolygonStruct *SegPl,
  571.                         PointType Segment[2])
  572. {
  573.     int i, Reverse, Res,
  574.     NumOfInter = 0;
  575.     RealType TInter[3], temp, Min, Max, *PtSeg0, *PtSeg1;
  576.     PointType Dir, Inter[2], SegDir, Pt1, Pt2;
  577.     IPVertexStruct *VInter[2], *Vnext,
  578.     *V = Pl -> PVertex;
  579.     InterSegmentStruct *PSeg;
  580.  
  581.     /* Find the segment direction vector: */
  582.     PT_SUB(SegDir, Segment[1], Segment[0]);
  583.  
  584. #ifdef DEBUG3
  585.     printf("Enter InterSegmentPoly\n");
  586. #endif /* DEBUG3 */
  587.  
  588.     do {
  589.     Vnext = V -> Pnext;
  590.     PT_SUB(Dir, Vnext -> Coord, V -> Coord);
  591.     /* Find the intersection of the segment with all the polygon edges: */
  592.     /* Note the t parameter value of the edge (temp) must be in [0..1]. */
  593.     if ((Res = CG2PointsFromLineLine(Segment[0], SegDir,
  594.         V -> Coord, Dir, Pt1, &TInter[NumOfInter], Pt2, &temp)) != 0 &&
  595.         (temp > 0.0 || BOOL_APX_EQ(temp, 0.0)) &&
  596.         (temp < 1.0 || BOOL_APX_EQ(temp, 1.0)) &&
  597.         BOOL_PT_APX_EQ(Pt1, Pt2) &&
  598.         (NumOfInter == 0 ||
  599.          (NumOfInter == 1 && !BOOL_APX_EQ(TInter[0], TInter[1])))) {
  600.         PT_COPY(Inter[NumOfInter], Pt1);
  601.         VInter[NumOfInter++] = V;/* Save pointer to intersected edge. */
  602.     }
  603.     else {
  604.         /* If Res == 0 its parallel to edge. If distance is zero then    */
  605.         /* line is on the edge line itself - quit from this one!         */
  606.         if (!Res && CGDistPointLine(Segment[0], V -> Coord, Dir) <
  607.                                 BOOL_EPSILON) {
  608.         /* Wipe out adjacency of this vertex if not shared any more  */
  609.         IPVertexStruct *Vtemp;
  610.  
  611.         if (V -> PAdj == NULL || BoolVerifyShareEdge(V, V -> PAdj))
  612.             return NULL;
  613.  
  614.         Vtemp = V -> PAdj -> PVertex;
  615.         do {/* Find the edge on the other polygon to wipe out first. */
  616.             if (Vtemp -> PAdj == Pl) {
  617.             Vtemp -> PAdj = NULL;
  618.             break;
  619.             }
  620.             Vtemp = Vtemp -> Pnext;
  621.         }
  622.         while (Vtemp != NULL && Vtemp != V -> PAdj -> PVertex);
  623.         V -> PAdj = NULL;        /* And wipe out ours also... */
  624.         return NULL;
  625.         }
  626.     }
  627.  
  628.     V = Vnext;
  629.     }
  630.     while (V != NULL && V != Pl -> PVertex);
  631.  
  632.     switch (NumOfInter) {
  633.     case 0:
  634.         return NULL;
  635.     case 1:
  636.         /* One intersection is possible if segment intersects one vertex */
  637.         /* of polygon and all other vertices are on same side of segment.*/
  638.         return NULL;
  639.     case 2:
  640.         /* In order the segment to really intersect the polygon, it must */
  641.         /* at list part of t in [0..1] in the polygon. Test it:         */
  642.         Min = MIN(TInter[0], TInter[1]);
  643.         Max = MAX(TInter[0], TInter[1]);
  644.         Reverse = TInter[0] > TInter[1];
  645.         if (Min >= 1.0 || BOOL_APX_EQ(Min, 1.0) ||
  646.         Max <= 0.0 || BOOL_APX_EQ(Max, 0.0))
  647.         return NULL;
  648.  
  649.         PSeg = (InterSegmentStruct *)
  650.         IritMalloc(sizeof(InterSegmentStruct));
  651.         PSeg -> Pl = SegPl;     /* Pointer to other (intersect) polygon. */
  652.  
  653.         /* Handle the Min end point: */
  654.         if (BOOL_APX_EQ(Min, 0.0)) {
  655.         PtSeg0 = Segment[0];
  656.         PSeg -> V[0] = (Reverse ? VInter[1] : VInter[0]);
  657.         }
  658.         else if (Min < 0.0) {
  659.         PtSeg0 = Segment[0];
  660.         PSeg -> V[0] = NULL;             /* End is internal. */
  661.         }
  662.         else { /* Min > 0.0 */
  663.         PtSeg0 = (Reverse ? Inter[1] : Inter[0]);
  664.         PSeg -> V[0] = (Reverse ? VInter[1] : VInter[0]);
  665.         }
  666.  
  667.         /* Handle the Max end point: */
  668.         if (BOOL_APX_EQ(Max, 1.0)) {
  669.         PtSeg1 = Segment[1];
  670.         PSeg -> V[1] = (Reverse ? VInter[0] : VInter[1]);
  671.         }
  672.         else if (Max > 1.0) {
  673.         PtSeg1 = Segment[1];
  674.         PSeg -> V[1] = NULL;             /* End is internal. */
  675.         }
  676.         else { /* Max < 1.0 */
  677.         PtSeg1 = (Reverse ? Inter[0] : Inter[1]);
  678.         PSeg -> V[1] = (Reverse ? VInter[0] : VInter[1]);
  679.         }
  680.  
  681.         PT_COPY(PSeg -> PtSeg[0], PtSeg0); /* The two segment end point. */
  682.             PT_COPY(PSeg -> PtSeg[1], PtSeg1);
  683.  
  684.         for (i = 0; i < 3; i++) {         /* Make zeros look nicer... */
  685.         if (ABS(PSeg -> PtSeg[0][i]) < BOOL_EPSILON)
  686.             PSeg -> PtSeg[0][i] = 0.0;
  687.         if (ABS(PSeg -> PtSeg[1][i]) < BOOL_EPSILON)
  688.             PSeg -> PtSeg[1][i] = 0.0;
  689.         }
  690.         if (BOOL_PT_APX_EQ(PSeg -> PtSeg[0], PSeg -> PtSeg[1])) {
  691.         IritFree((VoidPtr) PSeg);
  692.         return NULL;
  693.         }
  694.         return PSeg;
  695.     }
  696.     return NULL;                    /* Makes warning silent. */
  697. }
  698.  
  699. /*****************************************************************************
  700. * DESCRIPTION:                                                               M
  701. *   Given a polygon with the intersection list, creates the polylines        M
  702. * loop(s) out of it, which can be one of the two:                 M
  703. * 1. Closed loop - all the intersections create a loop in one polygon.         M
  704. * 2. Open polyline - if the intersections cross the polygon boundary. In     M
  705. *    this case the two end point of the polyline, must lay on polygon         M
  706. *    boundary.                                     M
  707. *                                         M
  708. * In both cases, the polyline will be as follows:                 M
  709. * First point at first list element at PtSeg[0] (see InterSegmentStruct).    M
  710. * Second point at first list element at PtSeg[1] (see InterSegmentStruct).   M
  711. * Point i at list element (i-1) at PtSeg[0] (PtSeg[1] is not used!).         M
  712. * In the closed loop case the last point is equal to first.             M
  713. * Both cases returns NULL terminated list.                     M
  714. *                                                                            *
  715. * PARAMETERS:                                                                M
  716. *   Pl:         Polygon with intersection information in its PAux slot.      M
  717. *   PClosed:    To be updated with the closed loops found in Pl.             M
  718. *   POpen:      To be updated with the open loops found in Pl.               M
  719. *                                                                            *
  720. * RETURN VALUE:                                                              M
  721. *   void                                                                     M
  722. *                                                                            *
  723. * KEYWORDS:                                                                  M
  724. *   BoolLoopsFromInterList                                                   M
  725. *****************************************************************************/
  726. void BoolLoopsFromInterList(IPPolygonStruct *Pl,
  727.                 InterSegListStruct **PClosed,
  728.                 InterSegListStruct **POpen)
  729. {
  730.     InterSegmentStruct *PSeg, *PSegHead, *PSegTemp, *PSegNewTemp;
  731.     InterSegListStruct *PSLTemp;
  732.  
  733. #ifdef DEBUG3
  734.     printf("Enter BoolLoopsFromInterList\n");
  735. #endif /* DEBUG3 */
  736.  
  737.     *PClosed = (*POpen) = NULL;
  738.  
  739.     if ((PSeg = (InterSegmentStruct *) Pl -> PAux) == NULL) {
  740.     return;
  741.     }
  742.     else {
  743.     /* Do intersect - find if there are closed loops and/or open ones:   */
  744.     Pl -> PAux = NULL;
  745.     while (TRUE) {
  746.         /* First, we look for open loops - scans linearly (maybe should  */
  747.         /* be done more efficiently) for segment on boundary and start   */
  748.         /* build chain from it (up to the other end, on the boundary).   */
  749.         PSegHead = PSeg;
  750.         while (PSegHead) {
  751.         if (PSegHead -> V[0] != NULL || PSegHead -> V[1] != NULL) {
  752.             /* Found one - make it in correct order, del. from list: */
  753.             if (PSegHead -> V[0] == NULL)
  754.             SwapPointInterList(PSegHead);
  755.             DeleteSegInterList(PSegHead, &PSeg);
  756.             break;
  757.         }
  758.         else
  759.             PSegHead = PSegHead -> Pnext;
  760.         }
  761.         if (PSegHead == NULL)
  762.         break;                /* No more open segments here... */
  763.  
  764.         PSegTemp = PSegHead;
  765.         while (PSegTemp -> V[1] == NULL) {
  766.         /* Search for matching to the second boundary end: */
  767.         PSegNewTemp = FindMatchInterList(PSegTemp -> PtSeg[1], &PSeg);
  768.         PSegTemp -> Pnext = PSegNewTemp;
  769.         PSegTemp = PSegNewTemp;
  770.         }
  771.         PSegTemp -> Pnext = NULL;
  772.         PSLTemp = (InterSegListStruct *)
  773.         IritMalloc(sizeof(InterSegListStruct));
  774.         PSLTemp -> PISeg = PSegHead;
  775.         PSLTemp -> PISegMaxX = NULL;
  776.         PSLTemp -> Pnext = *POpen;
  777.         *POpen = PSLTemp;
  778.     }
  779.  
  780.     while (TRUE) {
  781.         /* Now, we look for closed loops - pick one segment and search   */
  782.         /* for matching until you close the loop.                 */
  783.         PSegHead = PSeg;
  784.         if (PSegHead == NULL)
  785.         break;              /* No more closed segments here... */
  786.         DeleteSegInterList(PSegHead, &PSeg);
  787.  
  788.         PSegTemp = PSegHead;
  789.         while (!BOOL_PT_APX_EQ(PSegTemp -> PtSeg[1],
  790.                    PSegHead -> PtSeg[0])) {
  791.         /* Search for matching until we back at first point: */
  792.         PSegNewTemp = FindMatchInterList(PSegTemp -> PtSeg[1], &PSeg);
  793.         PSegTemp -> Pnext = PSegNewTemp;
  794.         PSegTemp = PSegNewTemp;
  795.         }
  796.         PSegTemp -> Pnext = NULL;
  797.         PSLTemp = (InterSegListStruct *)
  798.         IritMalloc(sizeof(InterSegListStruct));
  799.         PSLTemp -> PISeg = PSegHead;
  800.         PSLTemp -> PISegMaxX = NULL;
  801.         PSLTemp -> Pnext = *PClosed;
  802.         *PClosed = PSLTemp;
  803.     }
  804.     }
  805.  
  806. #ifdef DEBUG3
  807.     printf("Exit BoolLoopsFromInterList\n");
  808. #endif /* DEBUG3 */
  809. }
  810.  
  811. /*****************************************************************************
  812. * DESCRIPTION:                                                               *
  813. * Swaps the two points in an InterSegmentStruct (modifies PtSeg & V entries) *
  814. *                                                                            *
  815. * PARAMETERS:                                                                *
  816. *   PSeg:   To swap the two points in it.                                    *
  817. *                                                                            *
  818. * RETURN VALUE:                                                              *
  819. *   void                                                                     *
  820. *****************************************************************************/
  821. static void SwapPointInterList(InterSegmentStruct *PSeg)
  822. {
  823.     PointType Pt;
  824.     IPVertexStruct *V;
  825.  
  826.     PT_COPY(Pt,              PSeg -> PtSeg[0]);
  827.     PT_COPY(PSeg -> PtSeg[0], PSeg -> PtSeg[1]);
  828.     PT_COPY(PSeg -> PtSeg[1], Pt);
  829.  
  830.     V         = PSeg -> V[0];
  831.     PSeg -> V[0] = PSeg -> V[1];
  832.     PSeg -> V[1] = V;
  833. }
  834.  
  835. /*****************************************************************************
  836. * DESCRIPTION:                                                               *
  837. *   Deletes one InterSegment PSeg, from InterSegmentList PSegList.         *
  838. *                                                                            *
  839. * PARAMETERS:                                                                *
  840. *   PSeg:         To be deleted from the list (not delete itself).           *
  841. *   PSegList:     List containing PSeg. Updated in place.                    *
  842. *                                                                            *
  843. * RETURN VALUE:                                                              *
  844. *   void                                                                     *
  845. *****************************************************************************/
  846. static void DeleteSegInterList(InterSegmentStruct *PSeg,
  847.                    InterSegmentStruct **PSegList)
  848. {
  849.     InterSegmentStruct *PSegTemp;
  850.  
  851.     if (*PSegList == PSeg) { /* Its the first one - simply advance list ptr: */
  852.     *PSegList = (*PSegList) -> Pnext;
  853.     }
  854.     else {
  855.     PSegTemp = (*PSegList);
  856.     while (PSegTemp -> Pnext != NULL && PSegTemp -> Pnext != PSeg)
  857.         PSegTemp = PSegTemp -> Pnext;
  858.     if (PSegTemp -> Pnext == PSeg)
  859.         PSegTemp -> Pnext = PSegTemp -> Pnext -> Pnext;
  860.     else
  861.         IritFatalError("DeleteSegInterList: element to delete not found");
  862.     }
  863. }
  864.  
  865. /*****************************************************************************
  866. * DESCRIPTION:                                                               *
  867. *   Searches for matching point, in the given inter segment list. Returns    *
  868. * the pointer to that element after swapping its points if needed (the match *
  869. * must be with point 0 of new segment returned), and deletes it from list.   *
  870. *                                                                            *
  871. * PARAMETERS:                                                                *
  872. *   Pt:          To find a match for.                                        *
  873. *   PSegList:    To search for a match for Pt at.                            *
  874. *                                                                            *
  875. * RETURN VALUE:                                                              *
  876. *   InterSegmentStruct:   Matching edge with mtching point to Pt, if any.    *
  877. *****************************************************************************/
  878. static InterSegmentStruct *FindMatchInterList(PointType Pt,
  879.                           InterSegmentStruct **PSegList)
  880. {
  881.     InterSegmentStruct
  882.     *PSegTemp = (*PSegList);
  883.  
  884. #ifdef DEBUG3
  885.     printf("Enter FindMatchInterList\n");
  886. #endif /* DEBUG3 */
  887.  
  888.     while (PSegTemp != NULL) {
  889.     if (BOOL_PT_APX_EQ(Pt, PSegTemp -> PtSeg[0])) {
  890.         DeleteSegInterList(PSegTemp, PSegList);
  891.         return PSegTemp;
  892.     }
  893.     if (BOOL_PT_APX_EQ(Pt, PSegTemp -> PtSeg[1])) {
  894.         DeleteSegInterList(PSegTemp, PSegList);
  895.         SwapPointInterList(PSegTemp);
  896.         return PSegTemp;
  897.     }
  898.     PSegTemp = PSegTemp -> Pnext;
  899.     }
  900.  
  901.     IritFatalError("FindMatchInterList: No match found - Empty Object Result");
  902.     return NULL;
  903. }
  904.  
  905. /*****************************************************************************
  906. * DESCRIPTION:                                                               M
  907. *   Sorts the open loops of given polygon to an order that can be used in    M
  908. * subdividing into sub polygons later (see comment of BoolExtractPolygons).  M
  909. *   This order is such that each loops will have no other loop between its   M
  910. * end points, if we walk along the polygon in the (linked list direction)    M
  911. * perimeter from one end to the other, before it. For example:             M
  912. *             -----------------------------L3                 V
  913. *        |  ---------------L1  -----L2 |          --------L4   --L5   V
  914. *        | |               |  |     |  |         |        |   |  |    V
  915. *      P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 V
  916. * In this case, any order such that L1, L2 are before L3 will do. Obviously  M
  917. * this is not a total order, and they are few correct ways to sort it.         M
  918. * Algorithm:                                     M
  919. *   For each open loop, for each of its two end, evaluate a RealType key for M
  920. * the end point P between segment P(i) .. P(i+1) to be i + t, where:         M
  921. * t is the ratio  (P - P(i)) / (P(i+1) - P(i)) . This maps the all perimeter M
  922. * of the polygon onto 0..N-1, where N is number of vertices of that polygon. M
  923. *   Sort the keys, and while they are keys in data sturcture, search and     M
  924. * remove a consecutive pair of keys assosiated with same loop, and output it.M
  925. *   Note that each open loop point sequence is tested to be such that it     M
  926. * starts on the first point (first and second along vertex list) on polygon  M
  927. * perimeter, and the sequence end is on the second point, and the sequence   M
  928. * is reversed if not so. This order will make the replacement of the         M
  929. * perimeter from first to second points by the open loop much easier.         M
  930. *   This may be real problem if there are two intersection points almost     M
  931. * identical - floating point errors may cause it to loop forever. We use     M
  932. * some reordering heuristics in this case, and return fatal error if fail!   M
  933. *                                                                            *
  934. * PARAMETERS:                                                                M
  935. *   Pl:       To sort the loops for.                                         M
  936. *   POpen:    The set of open loops. Updated in place.                       M
  937. *                                                                            *
  938. * RETURN VALUE:                                                              M
  939. *   void                                                                     M
  940. *                                                                            *
  941. * KEYWORDS:                                                                  M
  942. *   BoolSortOpenInterList                                                    M
  943. *****************************************************************************/
  944. void BoolSortOpenInterList(IPPolygonStruct *Pl, InterSegListStruct **POpen)
  945. {
  946.     int Found = TRUE,
  947.     ReOrderFirst = FALSE,
  948.     NumOfReOrders = 0;
  949.     RealType Key1, Key2;
  950.     InterSegmentStruct *PSeg;
  951.     InterSegListStruct *PLSeg, *PLNext,
  952.     *PResTemp = NULL,
  953.     *PResHead = NULL;
  954.     SortOpenStruct *PSTemp, *PSTemp1, *PSTemp2,
  955.     *PSHead = NULL;
  956.  
  957. #ifdef DEBUG3
  958.     printf("Enter BoolSortOpenInterList\n");
  959. #endif /* DEBUG3 */
  960.  
  961.     PLSeg = (*POpen);
  962.     while (PLSeg != NULL) {    /* Evaluate the two end keys and insert them: */
  963.         PSeg = PLSeg -> PISeg;
  964.     PLNext = PLSeg -> Pnext;
  965.     PLSeg -> Pnext = NULL;
  966.  
  967.     PSTemp1 = (SortOpenStruct *) IritMalloc(sizeof(SortOpenStruct));
  968.     PSTemp1 -> PLSeg = PLSeg;
  969.     /* Insert PSTemp1 into PLHead list according to position of Pt in Pl.*/
  970.     Key1 = SortOpenInsertOne(&PSHead, PSTemp1, PSeg -> PtSeg[0],
  971.                            PSeg -> V[0], Pl);
  972.  
  973.     while (PSeg -> Pnext != NULL) PSeg = PSeg -> Pnext; /* Go other end. */
  974.     PSTemp2 = (SortOpenStruct *) IritMalloc(sizeof(SortOpenStruct));
  975.     PSTemp2 -> PLSeg = PLSeg;
  976.     /* Insert PSTemp2 into PLHead list according to position of Pt in Pl.*/
  977.     Key2 = SortOpenInsertOne(&PSHead, PSTemp2, PSeg -> PtSeg[1],
  978.                            PSeg -> V[1], Pl);
  979.  
  980.     if (Key1 > Key2)          /* Reverse the open loop points order: */
  981.         SortOpenReverseLoop(PSTemp1);
  982.  
  983.     PLSeg = PLNext;
  984.     }
  985.  
  986.     while (PSHead != NULL) {    /* Search for consecutive pair of same loop. */
  987.     if (NumOfReOrders++ > 10)
  988.         IritFatalError("BoolSortOpenInterList: fail to sort intersection list");
  989.     if (Found)
  990.         NumOfReOrders = 0;
  991.  
  992.     Found = FALSE;
  993.     PSTemp = PSHead;
  994.     if (PSTemp -> PLSeg == PSTemp -> Pnext -> PLSeg) { /* First is pair! */
  995.         if (PResHead == NULL)
  996.         PResHead = PResTemp = PSTemp -> PLSeg;
  997.         else {
  998.         PResTemp -> Pnext = PSTemp -> PLSeg;
  999.         PResTemp = PSTemp -> PLSeg;
  1000.         }
  1001.         PSHead = PSHead -> Pnext -> Pnext;         /* Skip the first pair. */
  1002.         IritFree((VoidPtr) PSTemp -> Pnext);
  1003.         IritFree((VoidPtr) PSTemp);
  1004.         Found = TRUE;
  1005.         continue;
  1006.     }
  1007.     /* If we are here, first pair is not of same loop - search on: */
  1008.     while (PSTemp -> Pnext -> Pnext != NULL) {
  1009.         if (PSTemp -> Pnext -> PLSeg == PSTemp -> Pnext -> Pnext -> PLSeg) {
  1010.         if (PResHead == NULL)
  1011.             PResHead = PResTemp = PSTemp -> Pnext -> PLSeg;
  1012.         else {
  1013.             PResTemp -> Pnext = PSTemp -> Pnext -> PLSeg;
  1014.             PResTemp = PSTemp -> Pnext -> PLSeg;
  1015.         }
  1016.         PSTemp2 = PSTemp -> Pnext;
  1017.         PSTemp -> Pnext = PSTemp -> Pnext -> Pnext -> Pnext;
  1018.         IritFree((VoidPtr) PSTemp2 -> Pnext);
  1019.         IritFree((VoidPtr) PSTemp2);
  1020.         Found = TRUE;
  1021.         break;
  1022.         }
  1023.         PSTemp = PSTemp -> Pnext;
  1024.     }
  1025.     /* The only way we might found nothing is in floating point round */
  1026.     /* off error - two curve ends has almost the same Key...      */
  1027.     /* Note, obviously, that there are at list 4 entries in list.     */
  1028.     if (!Found) {
  1029.         if (!ReOrderFirst &&
  1030.         BOOL_APX_EQ(PSHead -> Pnext -> Key, PSHead -> Key)) {
  1031.         ReOrderFirst = TRUE;
  1032.         PSTemp1 = PSHead -> Pnext;
  1033.         PSHead -> Pnext = PSTemp1 -> Pnext;
  1034.         PSTemp1 -> Pnext = PSHead;
  1035.         PSHead = PSTemp1;
  1036.         continue;
  1037.         }
  1038.         else
  1039.         ReOrderFirst = FALSE;
  1040.         PSTemp = PSHead;
  1041.         while (PSTemp -> Pnext -> Pnext != NULL) {
  1042.         if (BOOL_APX_EQ(PSTemp -> Pnext -> Key,
  1043.                PSTemp -> Pnext -> Pnext -> Key)) {
  1044.             PSTemp1 = PSTemp -> Pnext;
  1045.             PSTemp2 = PSTemp1 -> Pnext;
  1046.             PSTemp1 -> Pnext = PSTemp2 -> Pnext;
  1047.             PSTemp2 -> Pnext = PSTemp1;
  1048.             PSTemp -> Pnext = PSTemp2;
  1049.             break;
  1050.         }
  1051.         PSTemp = PSTemp -> Pnext;
  1052.         }
  1053.     }
  1054.     }
  1055.  
  1056.     *POpen = PResHead;
  1057.  
  1058. #ifdef DEBUG3
  1059.     printf("Exit BoolSortOpenInterList\n");
  1060. #endif /* DEBUG3 */
  1061. }
  1062.  
  1063. /*****************************************************************************
  1064. * DESCRIPTION:                                                               *
  1065. *   Reverses the order of the open loop pointed by PSHead.             *
  1066. *                                                                            *
  1067. * PARAMETERS:                                                                *
  1068. *   PSHead:    Head of open loop to be reversed, in place.                   *
  1069. *                                                                            *
  1070. * RETURN VALUE:                                                              *
  1071. *   void                                                                     *
  1072. *****************************************************************************/
  1073. static void SortOpenReverseLoop(SortOpenStruct *PSHead)
  1074. {
  1075.     InterSegmentStruct *PIHead, *PITemp,
  1076.     *PINewHead = NULL;
  1077.  
  1078.     PIHead = PSHead -> PLSeg -> PISeg;
  1079.  
  1080.     while (PIHead != NULL) {
  1081.     PITemp = PIHead;
  1082.     PIHead = PIHead -> Pnext;
  1083.     SwapPointInterList(PITemp);
  1084.     PITemp -> Pnext = PINewHead;
  1085.     PINewHead = PITemp;
  1086.     }
  1087.  
  1088.     PSHead -> PLSeg -> PISeg = PINewHead;
  1089. }
  1090.  
  1091. /*****************************************************************************
  1092. * DESCRIPTION:                                                               *
  1093. *   Inserts new loop PSTemp, defines key by Pt and V (V defines the edge     *
  1094. * and Pt is the points on it), into (decreasingly) ordered list PSHead.         *
  1095. *                                                                            *
  1096. * PARAMETERS:                                                                *
  1097. *   PSHead:      Ordered list of loops.                                      *
  1098. *   PSTemp:      Loop to be inserted.                                        *
  1099. *   Pt, V:       Defining the order's key.                                   *
  1100. *   Pl:          The polygon that is responsible for all the mess.           *
  1101. *                                                                            *
  1102. * RETURN VALUE:                                                              *
  1103. *   RealType:    The key that the new loop was inserted according to.        *
  1104. *****************************************************************************/
  1105. static RealType SortOpenInsertOne(SortOpenStruct **PSHead,
  1106.                   SortOpenStruct *PSTemp,
  1107.                   PointType Pt,
  1108.                   IPVertexStruct *V,
  1109.                   IPPolygonStruct *Pl)
  1110. {
  1111.     int i = 0;
  1112.     RealType Key;
  1113.     PointType Pt1, Pt2;
  1114.     IPVertexStruct
  1115.     *VTemp = Pl -> PVertex;
  1116.     SortOpenStruct *PSTail;
  1117.  
  1118.     PSTemp -> Pnext = NULL;
  1119.  
  1120.     while (VTemp != V && VTemp != NULL) {
  1121.     i++;
  1122.     VTemp = VTemp -> Pnext;
  1123.     }
  1124.     if (VTemp == NULL)
  1125.     IritFatalError("SortOpenInsertOne: fail to find vertex");
  1126.  
  1127.     PT_SUB(Pt1, V -> Pnext -> Coord, V -> Coord);
  1128.     PT_SUB(Pt2, Pt, V -> Coord);
  1129.     Key = PSTemp -> Key = i + PT_LENGTH(Pt2) / PT_LENGTH(Pt1);
  1130.  
  1131.     /* Now insert PSTemp into the ordered list: */
  1132.     if (*PSHead == NULL) {
  1133.     *PSHead = PSTemp;
  1134.     return Key;
  1135.     }
  1136.     if (PSTemp -> Key > (*PSHead) -> Key) {         /* Insert as first? */
  1137.     PSTemp -> Pnext = (*PSHead);
  1138.     *PSHead = PSTemp;
  1139.     return Key;
  1140.     }
  1141.     PSTail = (*PSHead);
  1142.     while (PSTail -> Pnext != NULL && PSTemp -> Key < PSTail -> Pnext -> Key)
  1143.     PSTail = PSTail -> Pnext;
  1144.     PSTemp -> Pnext = PSTail -> Pnext;
  1145.     PSTail -> Pnext = PSTemp;
  1146.  
  1147.     return Key;
  1148. }
  1149.  
  1150. #ifdef DEBUG2
  1151.  
  1152. /*****************************************************************************
  1153. * DESCRIPTION:                                                               *
  1154. *   Print the content of the given vertex list, to standard output.         *
  1155. *                                                                            *
  1156. * PARAMETERS:                                                                *
  1157. *   V:       The vertex list to be printed.                                  *
  1158. *                                                                            *
  1159. * RETURN VALUE:                                                              *
  1160. *   void                                                                     *
  1161. *****************************************************************************/
  1162. static void PrintVrtxList(IPVertexStruct *V)
  1163. {
  1164.     IPVertexStruct
  1165.     *VHead = V;
  1166.  
  1167.     do {
  1168.     printf("    %12lf %12lf %12lf\n",
  1169.            V -> Coord[0], V -> Coord[1], V -> Coord[2]);
  1170.     V = V -> Pnext;
  1171.     }
  1172.     while (V!= NULL && V != VHead);
  1173. }
  1174.  
  1175. /*****************************************************************************
  1176. * DESCRIPTION:                                                               *
  1177. *   Print the content of the given InterSegment list, to standard output.    *
  1178. *                                                                            *
  1179. * PARAMETERS:                                                                *
  1180. *   PInt:       The InterSegment list to be printed.                         *
  1181. *                                                                            *
  1182. * RETURN VALUE:                                                              *
  1183. *   void                                                                     *
  1184. *****************************************************************************/
  1185. static void PrintInterList(InterSegmentStruct *PInt)
  1186. {
  1187.     printf("INTER SEGMENT LIST:\n");
  1188.  
  1189.     if (PInt)
  1190.     printf("Entry vertex pointer %p\n", PInt -> V[0]);
  1191.     while (PInt) {
  1192.     printf("%9lg %9lg %9lg (%04x), %9lg %9lg %9lg (%04x)\n",
  1193.         PInt->PtSeg[0][0], PInt->PtSeg[0][1], PInt->PtSeg[0][2],
  1194.         PInt->V[0],
  1195.         PInt->PtSeg[1][0], PInt->PtSeg[1][1], PInt->PtSeg[1][2],
  1196.         PInt->V[1]);
  1197.     if (PInt -> Pnext == NULL)
  1198.         printf("Exit vertex pointer %p\n", PInt -> V[1]);
  1199.  
  1200.     PInt = PInt -> Pnext;
  1201.     }
  1202. }
  1203.  
  1204. #endif /* DEBUG2 */
  1205.